# Tri par sélection

## Introduction

Le tri fusion est un tri efficace et stable qui applique le principe "diviser
pour règner". Il consiste à découper le tableau en deux, à trier chaque sous-partie,
puis à fusionner. C'est un algorithme récursif. Exemple :

| indices | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| ------- | - | - | - | - | - | - | - |
| valeurs | 3 | 6 | 1 | 5 | 2 | 2 | 4 |

Au premier appel, on découpe le tableau en deux (partage au milieu, soit au
niveau de l'indice 3, on on rappèle la fonction entre les indices 0 à 3 et
4 à 6, ce qui permettra d'obtenir deux sous-tableaux triés :

| indices | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| ------- | - | - | - | - | - | - | - |
| valeurs | 1 | 3 | 6 | 2 | 2 | 4 | 5 |

Il reste à fusionner les sous-parties `[1, 3, 6]` et `[2, 2, 4, 5]`.

La récursion s'arrête (cas de base) quand la taille du sous-tableau est inférieure à 2.


### Opération de fusion

*Plusieurs algorithmes sont possibles pour cette opération, à sélectioner
selon le compromis temps-mémoire.*

L'algorithme utilise trois tableaux `tab`, `left` et `right`, les deux derniers
étant des sous-tableaux du premier (copies - ce qui à un coup mémoire) :

- `tab` = `[1, 3, 6, 2, 2, 4, 5]`, `i` est l'indice du prochain élément à écraser ;
- `left` = `[1, 3, 6]` ; `iLeft` est l'indice du prochain élément de ce tableau à insérer ;
- et `right` = `[2, 2, 4, 5]`, avec l'indice `iRight`.


- A la première itération, `iRight` et iLeft valent 0, et l'algorithme compare
`left[iLeft]` (1) à `right[iRight]` (2), et place le plus petit (1) puis incrémente
l'indice correspondant (ici `iLeft`).

A la deuxième itération, `iLeft` vaut 1 et `left[iLeft]` vaut 3. Par conséquent
la valeur à placer est 2, et cette fois c'est `iRight` qui est incrémenté :

| indices | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| ------- | - | - | - | - | - | - | - |
| valeurs | 1 | 2 | / | / | / | / | / |

Et ainsi de suite.


## Complexité

La complexité en temps de calcul de cet algorithme est en `O(n.log2(n))` :
le tableau est divisé en 2 `log2(n)` fois, et à chaque niveau de récursion,
ce sont `n` éléments qui sont fusionnées.


## Code des fonctions de fusion

Pour des raisons de simplicité et de qualité, ces fonctions sont séparées de
l'algorithme de tri.

```python
from typing import List
import math #pour le calcul de la complexité théorique

def fusionCopie(tab : List[int], inf : int, sup : int) -> List[int]:
    """
    @param tab le tableau à fusionner, en entrée-sortie
    @param inf la borne inférieure de la zone à fusionner
    @param inf la borne supérieure de la zone à fusionner
    prérequis: le calcul du milieu (séparation gauche-droite) doit être le
               même que dans la fonction appelante: mid = inf + (sup - inf) // 2
    @return le tableau fusionné (pour doctests)

    >>> fusionCopie([1, 5, 9, 2, 3, 4, 5], 0, 7)
    [1, 2, 3, 4, 5, 5, 9]
    """
    global cout                 #CPLX
    mid = inf + (sup - inf) // 2
    left = tab[inf:mid] #copie (coût mémoire)
    iLeft = 0
    right = tab[mid:sup]
    iRight = 0
    for i in range(inf, sup): #fusion entre inf et sup
        cout += 1               #CPLX
        if iLeft != len(left) and (iRight == len(right) or left[iLeft] < right[iRight]):
            tab[i] = left[iLeft]
            iLeft += 1
        else:
            tab[i] = right[iRight]
            iRight += 1
    return tab
```

Autre algorithme, avec tri en place — sans copie (mémoire), mais avec possible
décalage d'éléments pour l'insertion :

```python
def fusionEnPlace(tab : List[int], inf : int, sup : int) -> List[int]:
    """
    @param tab le tableau à fusionner, en entrée-sortie
    @param inf la borne inférieure de la zone à fusionner
    @param inf la borne supérieure de la zone à fusionner
    prérequis: le calcul du milieu (séparation gauche-droite) doit être le
               même que dans la fonction appelante: mid = inf + (sup - inf) // 2
    @return le tableau fusionné (pour doctests)
    >>> fusionEnPlace([], 0, 0)
    []
    >>> fusionEnPlace([1], 0, 1)
    [1]
    >>> fusionEnPlace([2, 1], 0, 2)
    [1, 2]
    >>> fusionEnPlace([0, 2, 1, 0], 1, 3)
    [0, 1, 2, 0]
    >>> fusionEnPlace([1, 0, 3, 2], 2, 4)
    [1, 0, 2, 3]
    >>> fusionEnPlace([0, 2, 1, 3], 0, 4)
    [0, 1, 2, 3]
    >>> fusionEnPlace([1, 5, 9, 2, 3, 4, 5], 0, 7)
    [1, 2, 3, 4, 5, 5, 9]
    """
    global cout                 #CPLX
    mid = inf + (sup - inf) // 2
    while inf != mid and mid != sup: #tant qu'une comparaison est possible (0(n))
        cout += 1               #CPLX
        if tab[inf] > tab[mid]:
            tmp = tab[mid]
            for k in range(mid, inf, -1): #décalage (coûteux en temps)
                cout += 1       #CPLX
                tab[k] = tab[k-1]
            tab[inf] = tmp #insertion
            mid += 1 #la partie gauche est agrandie
        inf += 1
    return tab
```

*Remarque : il est inutile de renvoyer le tableau (car il est modifié par
la fonction — cf passage en entrée-sortie), mais c'est plus pratique pour
écrire des doctests.*


## Code de la fonction de tri (version récursive)

*Cette fonction sert d'enveloppe pour initialiser la sous-fonction récursive.*

```python
def triFusionRec(tab : List[int]) -> List[int]:
    """
    trie le tableau selon la méthode du tri fusion, par ordre croissant
    version récursive
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triFusionRec([])
    []
    >>> triFusionRec([1])
    [1]
    >>> triFusionRec([2, 1])
    [1, 2]
    >>> triFusionRec([1, 3, 2])
    [1, 2, 3]
    >>> triFusionRec([4, 1, 3, 2])
    [1, 2, 3, 4]
    >>> triFusionRec([4, 2, 4, 2, 1, 4, 4])
    [1, 2, 2, 4, 4, 4, 4]
    """
    
    def triFusionRec_(tab : List[int], inf : int, sup : int):
        mid = inf + (sup - inf) // 2
        if inf + 1 != mid: #au moins 2 éléments à gauche
            triFusionRec_(tab, inf, mid)
        if mid + 1 != sup: #au moins 2 éléments à droite
            triFusionRec_(tab, mid, sup)
        # ~ fusionEnPlace(tab, inf, sup)    #essayer l'une
        fusionCopie(tab, inf, sup)          #ou l'autre version
    
    global cout #CPLX
    cout = 0    #CPLX
    if len(tab) > 1:
        triFusionRec_(tab, 0, len(tab))
    return tab

    
if __name__ == "__main__":
    cout = 0; import doctest; doctest.testmod()

    t1 = [1,3,9,5,8,4,7,2,6]
    triFusionRec(t1)
    print(t1)
    n = len(t1)
    print("complexité théorique : " + str(int(n*math.log2(n))))
    print("complexité effective : " + str(cout))
```


## Approndissement : version itérative

*Cette version utilise une pile <abbr title="Last In First Out">LIFO</abbr>
implémentée par tableau (`List`).*


```python
def triFusionIte(tab : List[int]) -> List[int]:
    """
    trie le tableau selon la méthode du tri fusion, par ordre croissant
    version itérative (récursion non terminale → requiert l'utilisation d'une pile)
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triFusionIte([])
    []
    >>> triFusionIte([1])
    [1]
    >>> triFusionIte([2, 1])
    [1, 2]
    >>> triFusionIte([1, 3, 2])
    [1, 2, 3]
    >>> triFusionIte([4, 1, 3, 2])
    [1, 2, 3, 4]
    >>> triFusionIte([4, 2, 4, 2, 1, 4, 4])
    [1, 2, 2, 4, 4, 4, 4]
    """
    global cout #CPLX
    cout = 0    #CPLX
    p = []
    if len(tab) > 1:
        p.append(("T", 0, len(tab)))
    
    while len(p) != 0:
        action, inf, sup = p.pop()
        if action == "T":
            p.append(("F", inf, sup))
            mid = inf + (sup - inf) // 2
            if inf + 1 != mid: #au moins 2 éléments à gauche
                p.append(("T", inf, mid))
            if mid + 1 != sup: #au moins 2 éléments à droite
                p.append(("T", mid, sup))
                    
        else: #action == "F"
            fusionEnPlace(tab, inf, sup)
    return tab
```